package Algorithms.DivideAndConquer_02;

/*
 * @Author 罗
 * @date 2020/3/28 - 10:57 下午
 */

/**
 * HashMap中，为什么桶的个数是2的n次方
 * 在将HashCode转为对应数组下标查找链表的时候，如果使用取模来查找数组下标，hashCode可表示的返回为42亿，
 * 取模的本质是减法的叠加，虽然有硬件电路优化，但还是速度太慢
 * 位运算比取模运算快 hashCode & (array.length-1)
 * array以16个桶为例，hashMap默认就是16个桶
 * array.length - 1 = 1 0000 - 1 = 1111
 * 再和32为的hashcode & 运算，可以直接截取hashCode的最后四位，就为数组的指定下标
 *
 * 如果桶的个数不是2的n次方，则在 & 运算的时候有的位始终位0，就出现查找对应桶的错误
 */

public class HanoiTower {

    public static void main(String[] args) {
        hanoiTower(3, 'a', 'b', 'c');
    }

    /**
     * @param number 第几个盘
     * @param a      柱子a 用于存放原盘
     * @param b      柱子b 中间辅助存储
     * @param c      柱子c 放置到的目标柱子
     */
    public static void hanoiTower(int number, char a, char b, char c) {
        if (number == 1) {
            /*
             * 只有一个盘的情况
             * */
            System.out.println("第" + number + "个盘从\t" + a + "\t->\t" + c);
        } else if (number >= 2) {
            /*
             * 两个盘及其以上的情况
             * 我们总是看作两个盘
             * 1.最下面的一个盘
             * 2.上面的所有盘
             *
             * number - 1  代表：上面的所有盘
             * 先把上面的所有盘，从a移动到b，由于打出的移动指令总是a->c
             *      因此需要把b和c交换位置，才能正确打出移动命令
             *
             * 移动过程中会使用到c，把c写在中间
             * */

            hanoiTower(number - 1, a, c, b);
            /*
             * 再把最下面的盘，从a移动到c
             * number 代表：最下面的盘
             * */
            System.out.println("第" + number + "个盘从\t" + a + "\t->\t" + c);
            /*
             * b塔的盘存放的是从a塔移动过来的上面的盘，a塔最下面的盘已经由上一步移动到c塔了
             * 最后再把b塔的所有盘移动到c塔
             *      由于打出的移动命令总是a->c，因此需要把a和b交换位置
             * */
            hanoiTower(number - 1, c, a, b);
        }
    }
}
